#include "../include/huffmanTree.h"
#include "../include/huffmanNode.h" // 包含HuffmanNode结构体的声明
#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<string, int>& freqMap) {
    // 最小堆
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;

    // 遍历频率映射表，将每个字符及其频率创建为节点，并加入最小堆
    for (auto pair : freqMap) {
        minHeap.push(new HuffmanNode(pair.first, pair.second));
    }

    // 当最小堆中节点数量不等于1时，继续合并节点
    while (minHeap.size() != 1) {
        // 取出频率最小的节点作为左子节点
        HuffmanNode* left = minHeap.top();
        minHeap.pop();

        // 取出频率次小的节点作为右子节点
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        // 合并左右子节点，创建一个新的节点，其频率为左右子节点频率之和
        HuffmanNode* merged = new HuffmanNode("", left->freq + right->freq);
        merged->left = left;
        merged->right = right;

        // 将合并后的节点加入最小堆
        minHeap.push(merged);
    }

    // 返回最小堆中唯一的节点，即哈夫曼树的根节点
    return minHeap.top();
}

// 清理哈夫曼树（如果需要）
// 这个函数用于释放动态分配的节点内存
// 注意：通常这种内存管理会在更高层次（如HuffmanTree类）进行
void freeHuffmanTree(HuffmanNode* root) {
    if (root == nullptr) return;
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    delete root;
}

// ... 可能还有其他辅助函数 ...